All of the material in this patent application is subject to copyright protection under the copyright laws of the United States and of other countries. As of the first effective filing date of the present application, this material is protected as unpublished material. However, permission to copy this material is hereby granted to the extent that the copyright owner has no objection to the facsimile reproduction by anyone of the patent documentation or patent disclosure, as it appears in the United States Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
Not Applicable
1. Field of the Invention
This invention relates to fault tolerant digital communications systems, in general, and more specifically to fault tolerant packet transmission systems involved in the management of multicast communications. Also, this invention generally relates to the field of distributed computing, wherein a plurality of computer machines are interconnected within a communications network, and more specifically with fault tolerant distributed systems.
2. Description of the Related Art
The term multicast in this disclosure refers to the protocol specification defined by the Internet Engineering Task Force (IETF) in the Request for Comments (RFC) specification 1122. In the field of providing a reliable network for the transmission for multicast datagrams, the specification of the protocol is such that a multicast datagram that originated in one node is only propagated directly to other nodes which are connected to the same subnetwork of the node that originated the datagram. In order for a multicast datagram to be received in a node which is not directly connected in the same subnetwork of the node that originated the request, the multicast datagram needs to be xe2x80x9crouted.xe2x80x9d The routing operation involves the deployment of a routing node, termed a xe2x80x9crouterxe2x80x9d; or package switching node. The location of the package switching nodes, expressed as an Internet Protocol (IP) address, is included in the multicast datagrams.
Multicast is presently considered one of the most efficient protocol for network communications. The justification for this assertion is the fact that nodes which do not subscribe for a specific multicast group will not even receive messages sent to that group. This is a significant advantage over the broadcast, which makes all nodes receive a message, even if there is no subscriber. The receipt of extraneous messages in a node amounts to an unnecessary CPU overhead. However, with the efficiency of multicast, there are difficulties. To begin, multicast requires to be routed, so that a datagram can be forwarded to another subnetwork. Unfortunately, not all routers presently support multicast routing. Also, due to system administrators preferences, the availability of multicast routing can never be assumed. (routers may not be configured to route multicast, even if they support such routing).
One multicast routing method and system is disclosed in U.S. Pat. No. 5,361,256, entitled xe2x80x9cInter-Domain Multicast Routing,xe2x80x9d with inventors Doeringer et. al, issued Nov. 1, 1994 and assigned to International Business Machines for transmitting a message or data packet from a single sender to a plurality, i.e., a group of receivers, usually called multicasting, within a conventional unicast transmission network, i.e., a network basically not equipped to handed such multicast transmissions.
Another multicast method and system is disclosed in U.S. Pat. No. 5,778,187 entitled xe2x80x9cMulticasting Method and Apparatus,xe2x80x9d with inventors Monteiro et al., issued Jul. 7, 1998 and assigned to Netcast Communications Corp. for a scalable architecture for delivery of real-time information over a communications network. Embedded into the architecture is a control mechanism that provides for the management and administration of user who are to receive real-time information.
Another multicast method and system is disclosed in U.S. Pat. No. 5,355,371 entitled xe2x80x9cMulticast Communication Tree Creation and Control Method and Apparatus,xe2x80x9d with inventors Auerbach et al., issued Oct. 11, 1994 and assigned to International Business Machines for administration of the communication path making up the multicast tree in a communications network. The multicast tree itself has been separated form control and administration of the network.
Another multicast method and system is disclosed in U.S. Pat. No. 5,831,975 entitled xe2x80x9cSystem and Method for Hierarchical Multicast Routing in Self-Routing in ATM Networks,xe2x80x9d with inventors Chen et al., issued Nov. 3, 1998 and assigned to Lucent Technologies for an extension of the PNNI protocols to support hierarchical multicast routing and signaling for ATM networks. The invention utilizes an extension to a core-based tree algorithm. Instead of a single core node, core nodes are maintained in each peer-group and each level of the hierarchy.
Another multicast method and system is disclosed in U.S. Pat. No. 5,671,222 entitled xe2x80x9cMulticast Routing in Self-Routing Multistage Networksxe2x80x9d with inventors Chen et al., issued Nov. 3, 1998 and assigned to Lucent Technologies for multicasting an inlet data cell, received as part of a multicast request, through a self-routing multicast request into one or more intermediate multicast requests, each intermediate multicast request being a unique subset of the original multicast request which enable a non-blocking, self-routing distribution to a subset of the desired outlet of the original multicast request which enables a non-blocking, self-routing distribution to a subset of the desired outlet of the original multicast request in one or two passes through the network, and by generating a non-blocking multicast tree based on the intermediate multicast requests and routing the received inlet data cell to the desire outlet.
Another multicast method and system is disclosed in U.S. Pat. No. 4,807,224entitled xe2x80x9cMulticast Data Distribution System and Method,xe2x80x9d with inventors Naron et al., issued Feb. 21, 1989 for a data distribution system and method for the timely, efficient and reliable distribution of data to an unlimited number of remote receiver installations.
Another multicast method and system is disclosed in U.S. Pat. No. 5,790,522 entitled xe2x80x9cMethod and System for Performing Traffic Congestion Control In A Multicast Data Distribution System Network,xe2x80x9d with inventors Fichou et al., issued Aug. 4, 1998 for traffic congestion control is provided for a network node multiport switch capable of switching data packets of different priorities from input lines, via receive adapter, to output lines via transmit adapters.
In order to control the routing of the multicast datagrams, several algorithms exist, which will negotiate the ordering of the routing addresses in a multicast message. Such algorithms use the notion of xe2x80x9cmulticast trees.xe2x80x9d A multicast tree is determined by the way that the packets are routed through the routing nodes to reach specific destinations. In the case of a Wide Area Network (WAN), there are several ways of routing a datagram, since there are redundant links of routing nodes that form a communication path between any node to points in the WAN. The traditional multicast tree protocols are related to the task of finding an optimal path (of minimal cost) between any two destinations. A common problem that affects tree routing algorithms is that any of the routing nodes may fail due to hardware or software problems. In most cases the failure is not detected because there is no mechanism for monitoring the health of the routing nodes. Accordingly, a need exists to provide an efficient monitoring mechanism which informs every node in a network of the availability status of any other node in the network.
Another problem related to the routing of multicast messages is that traditionally most WAN do not support multicast communications. This can be especially problematic in a network topology where two or more LANs (Local Area Networks) are separated by a WAN. Accordingly, a need exists for a mechanism for routing multicast diagrams in a stand alone WAN or a WAN bridging two or more LANS.
Another problem related to the routing of multicast messages is that it becomes difficult to contain the spread of the routing of multicast messages. More specifically, it becomes very difficult to contain multicast traffic to only selected subnetworks, if they are attached to the same routing node. Also, as more routing nodes get added, subnetworks begin to receive duplicates of multicast datagrams. Accordingly, a need exists for a method and apparatus to keep communications to a minimum but at the same time leverage the benefits of multicast technology.
Still another problem related with multicast routing is that the shortest path optimization made by multicast tree algorithms may overload routing points which are connected to several nodes with an excess of datagram messages to forward. Typical multicast routing protocols do not take into account the balancing of the routing burden which is imposed to the routing nodes. Accordingly, a need for a method and apparatus to keep communication balanced between nodes while taking advantage of a multicast protocols.
Another aspect of the multicast technology is that not all hardware is capable of n routing multicast datagrams. In such cases, a technology which is called xe2x80x9ctunnelingxe2x80x9d is deployed. Tunneling is a way in which multicast datagrams are encapsulated in regular IP packets which are then transmitted using regular TCP/IP, which is a point to point protocol. Using tunneling, nodes which reside in different subnetworks can send multicast datagrams to each other. In this case, one node in each subnetwork will act as an endpoint for a TCP/IP tunnel which will forward the multicast datagrams between the subnetworks.
The problem that arises in the deployment of tunnels is that typically the configuration of the tunnel is fixed. Typically, it is a task performed by the administrator of the communications network. In this case, a disruption of multicast links will happen if the hardware in any of the tunneling endpoints fails. A problem similar to the one faced by multicast tree algorithms arises when any of the tunneling endpoints fails, and the communication path or multicast datagrams is broken. And because the configuration of tunneling endpoints is a manual operation, the recovery of communications requires a manual intervention of the network administrator. Accordingly, a need exists to provide an efficient mechanism for monitoring the health of the tunneling endpoints and for acting on their failure by establishing alternative tunneling endpoints with which multicast datagrams may be routed between subnetworks.
The problem of detecting hardware failures in a communications network, or in a distributed computing system is very difficult to solve. The solutions for these problems typically demand a high amount of network traffic for sending hardware status verification messages, also called xe2x80x9cheartbeatsxe2x80x9d. Typical heartbeating solutions are not based on multicast protocols, since the failure of the routing points amounts to a disruption in multicast communications. However, the use of non-multicast protocols, cannot take advantage of the flexibility of the multicast messages, which reduce network traffic and such non-multicast algorithms demand too much bandwidth from the communications network. Accordingly, a need exists for a routing mechanism for datagram messages which limits the scope of propagation of routing protocol messages to a specific set of nodes in the communication network and which balances the routing operations for each routing point.
Still other problems that exist with management of current communications networks is the need to provide a simple program that can work across a variety of disperse, distinct and non-homogeneous network architectures with a small code foot print to work in small computers and routers, but that provides a correct hierarchal structure that is self contained and to enable the leveraging of multicast tunneling structure which is capable of dynamically routing the multicast messages to the entire communications network, independently of the network topology. Therefore, a need exists to overcome these and other problems.
A method and apparatus for managing communications in a distributed computing system wherein a plurality of computers are interconnected with a communications network. At least a portion of the network is established as a subnetwork with at least one node attached to the subnetwork. The node in the subnetwork multicast a verification message over the subnetwork in which it is attached. A subnetwork leader for each subnetwork is identified and gathers the verification message sent from each node in the subnetwork. The subnetwork leader assembles each verification received into a subnetwork list. The subnetwork list is sent a node identified as the network leader. The network leader assembles each subnetwork list received into a master list and sends this master list out to the subnetwork leaders. In turn, the subnetwork leaders for each subnetwork multicast the master list out to each node.
In one embodiment, the communications between each subnetwork leader and the network leader is over multicast.
In another embodiment, a system and computer readable medium is disclosed to carry out the above method.